1. Field of the Invention
The present invention is relates generally to the field of high-speed digital data processing systems, and more particularly to systems and methods of routing packets in multiprocessor computer systems.
2. Background Information
High-end multiprocessor computer systems typically consist of nodes interconnected by physical communication links. Often the physical links connect the nodes in an n-dimensional topology. Router logic connected to the physical links routes packets through the interconnect network.
Performance of interconnect networks depends on routing policy and flow control policy. Routing policy determines the path taken by a packet from source to destination. Flow control policy determines how the packet moves along that path. According to Peh and Dally in “A Delay Model for Router Microarchitectures,” published January-February 2001 in IEEE Micro, flow control policy significantly shapes an interconnect network's performance by its selection of the packets that receive buffers and channels. A poor flow control policy can result in a network that saturates at 30% of capacity, while a good flow control policy enables a network to operate at 80% or higher capacity.
Virtual-channel flow control improves network performance by reducing the blocking of physical channels. It does this by associating two or more virtual channels with a physical channel. Blocking of one of the virtual channels does not block the physical channel. When a packet blocks while holding a virtual channel, other packets can traverse the physical channel through the other virtual channel.
As virtual channels are added, the complexity of routing packets through a router increases. What is needed is system and method for reducing the complexity of routing packets through the router while maintaining high packet throughput.